package com.he.test;

/**
 * @description: 递归实现N皇后问题
 * @Author: HCL
 * @Date: 2024/11/4 15:21
 */
public class QueenTest2 {

    final int N = 4;
    int[] q = new int[N + 1];//第i个皇后在第i行的q[i]列上

    int answer = 0;

    /**
     * @Description 判断皇后位置是否合法
     * @Author HCL
     * @Date 2024/11/4 15:22
     * @Param
     * @Return
     */
    boolean check(int j) {
        boolean flag = true;
        for (int i = 1; i < j; i++) {
            // 判断是否在同一行 或 对角线上
            if (q[i] == q[j] || Math.abs(i - j) == Math.abs(q[i] - q[j])) {
                flag = false;
            }
        }
        return flag;
    }

    /**
     * @Description 求解N皇后方案
     * @Author HCL
     * @Date 2024/11/4 15:35
     * @Param
     * @Return
     */
    void queen(int j) {
        //初始化
        for (int i = 1; i <= N; i++) {
            q[j] = i;

            if (check(j)) {//摆放位置合法时
                if (j == N) {//找到N皇后的一组解
                    answer++;
                    System.out.print("方案：");
                    for (int k = 1; k <= N; k++) {
                        System.out.print(q[k]);
                    }
                    System.out.println();
                } else {
                    queen(j + 1);//递归摆放下一个位置的皇后
                }
            }
        }
    }

    public static void main(String[] args) {
//        new QueenTest2().queue(1);
        new QueenTest2().queen(1);
    }
}
